

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x = 0) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right = nullptr) : val(x), left(left), right(right) {}
} TNode;

TNode* CreateTree()
{
    /*TNode* node4 = new TNode(3);
    TNode* node5 = new TNode(3);
    TNode* node6 = new TNode(7);
    TNode* node2 = new TNode(4, node4, node5);
    TNode* node3 = new TNode(2, node6);
    TNode* node1 = new TNode(5, node2, node3);

    return node1;*/

    TNode* node7 = new TNode(12);
    TNode* node8 = new TNode(8);
    TNode* node9 = new TNode(6);
    TNode* node10 = new TNode(2);
    TNode* node4 = new TNode(3, node7, node8);
    TNode* node5 = new TNode(7, node9);
    TNode* node6 = new TNode(9, nullptr, node10);
    TNode* node2 = new TNode(10, node4);
    TNode* node3 = new TNode(4, node5, node6);
    TNode* node1 = new TNode(1, node2, node3);

    return node1;
}

class Solution
{
public:
    bool isEvenOddTree(TreeNode* root)
    {
        queue<TreeNode*> q;
        q.push(root);

        int level = 0;
        while (!q.empty())
        {
            int sz = q.size();
            vector<int> v;

            while (sz--)
            {
                if (q.front()->left)
                    q.push(q.front()->left);
                if (q.front()->right)
                    q.push(q.front()->right);

                v.push_back(q.front()->val);
                q.pop();
            }

            sz = v.size();
            for (int i = 0; i < sz; ++i)
            {
                if (0 == level % 2)
                {
                    if (0 == v[i] % 2)
                        return false;

                    if (i < sz - 1)
                    {
                        if (v[i] >= v[i + 1])
                            return false;
                    }
                }
                else
                {
                    if (1 == v[i] % 2)
                        return false;

                    if (i < sz - 1)
                    {
                        if (v[i] <= v[i + 1])
                            return false;
                    }
                }
            }

            ++level;
        }

        return true;
    }

    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2)
    {
        int cnt[1001] = { 0 };
        int index = 0;

        for (auto i : arr1)
        {
            cnt[i]++;
        }

        for (auto i : arr2)
        {
            while (cnt[i]--)
            {
                arr1[index++] = i;
            }
        }

        for (int i = 0; i < 1001; ++i)
        {
            if (cnt[i] > 0)
            {
                while (cnt[i]--)
                {
                    arr1[index++] = i;
                }
            }
        }

        return arr1;
    }
};

int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
{
    *returnSize = arr1Size;

    int index = 0;
    int cnt[1001] = { 0 };

    for (int i = 0; i < arr1Size; ++i)
    {
        cnt[arr1[i]]++;
    }

    for (int i = 0; i < arr2Size; ++i)
    {
        while (cnt[arr2[i]]--)
        {
            arr1[index++] = arr2[i];
        }
    }

    for (int i = 0; i < 1001; ++i)
    {
        if (cnt[i] > 0)
        {
            while (cnt[i]--)
            {
                arr1[index++] = i;
            }
        }
    }

    return arr1;
}

void Test1(void)
{
    TNode* root = CreateTree();
    //TNode* root = new TNode(2);

    cout << Solution().isEvenOddTree(root) << endl;
}

int main()
{
    Test1();

	return 0;
}